/*
提交链接:https://leetcode.cn/problems/cherry-pickup-ii/description/
1463. 摘樱桃 II
赖德檀 2024/12/28
*/

class Solution {
public:
int n,m;
//三维数组visitde[i][j][k]  维护的是机器人1位置(i,j) 机器人2位置(i,k)
int dfs(vector<vector<int>>& grid,vector<vector<vector<int>>>& visited, int i,int j,int k)
{
    if(i==n||j>=m||j<0||k<0||k>=m) return 0;
    int t=visited[i][j][k];
    if (t != -1)  // 之前计算过
    return t;
    for (int j1 = j - 1; j1 <= j + 1; j1++) {
        for (int k1 = k - 1; k1 <= k + 1; k1++) {
            visited[i][j][k] = max(visited[i][j][k], dfs(grid,visited,i + 1, j1, k1));//两个机器人走不同路径
        }
    }
    visited[i][j][k]+=grid[i][j];//加上机器人当前位置的值
    if(k!=j)//机器人2的位置没有和1重叠
    visited[i][j][k]+=grid[i][k];
    return visited[i][j][k];
}

    int cherryPickup(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        vector<vector<vector<int>>>visited(n, vector<vector<int>>(m, vector<int>(m, -1))); 
        return dfs(grid,visited,0, 0, m - 1);
    }
};
